package solution.list;

import java.util.ArrayList;
import java.util.List;

import junit.framework.Assert;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class CopyLinkWithExtraPointer {

	class LinkNode {
		LinkNode extra;
		LinkNode next;
		String value;

		@Override
		public String toString() {
			String s = "";
			LinkNode ln = this;
			do {
				s += "<" + ln.value + ":"
						+ (ln.extra != null ? ln.extra.value : "") + ">, ";
				ln = ln.next;
			} while (ln != null);
			return s;
		}
	}

	/**
	 * Copy a link list with extra random pointer
	 * 
	 * http://www.sureinterview.com/shwqst/785002/703001
	 * 
	 * @param link
	 *            the original link.
	 * @return the copied link.
	 */
	LinkNode copyLink(LinkNode link) {
		if (link == null)
			return null;

		// (1) copy the link list and hook up after the original node.
		LinkNode p = link;
		do {
			LinkNode p2 = new LinkNode();
			p2.value = new String(p.value.toLowerCase());
			p2.next = p.next;
			p.next = p2;
			p = p2.next; // NOTE: p = p.next.next;
		} while (p != null);

		// (2) copy the link list and hook up after the original node.
		p = link;
		do {
			if (p.extra != null) {
				p.next.extra = p.extra.next;
			}
			p = p.next.next; // NOTE: p = p.next.next;
		} while (p != null);

		// (3) split the two link lists apart.
		p = link;
		LinkNode link2 = p.next;
		while (p.next != null) {
			LinkNode q = p.next;
			p.next = q.next;
			p = q;
		}
		return link2;
	}

	@Test
	public void test() {
		String[] data = new String[] { "A", "B", "C", "D", "E" };
		LinkNode hd = null;
		List<LinkNode> nodeList = new ArrayList<LinkNode>();
		for (int i = data.length - 1; i >= 0; i--) {
			LinkNode ln = new LinkNode();
			nodeList.add(0, ln);
			ln.next = hd;
			ln.value = data[i];
			hd = ln;
		}
		nodeList.get(2).extra = nodeList.get(0);
		nodeList.get(1).extra = nodeList.get(3);
		nodeList.get(4).extra = nodeList.get(4);

		LinkNode hd2 = copyLink(hd);
		String sHd = hd.toString(), sHd2 = hd2.toString();
		System.out.println(sHd);
		System.out.println(sHd2);
		Assert.assertEquals(sHd, sHd2.toUpperCase());
	}

}
